This paper considers the problem of routing and rebalancing a shared fleet ofautonomous (i.e., self-driving) vehicles providing on-demand mobility within acapacitated transportation network, where congestion might disrupt throughput.We model the problem within a network flow framework and show that underrelatively mild assumptions the rebalancing vehicles, if properly coordinated,do not lead to an increase in congestion (in stark contrast to common belief).From an algorithmic standpoint, such theoretical insight suggests that theproblem of routing customers and rebalancing vehicles can be decoupled, whichleads to a computationally-efficient routing and rebalancing algorithm for theautonomous vehicles. Numerical experiments and case studies corroborate ourtheoretical insights and show that the proposed algorithm outperformsstate-of-the-art point-to-point methods by avoiding excess congestion on theroad. Collectively, this paper provides a rigorous approach to the problem ofcongestion-aware, system-wide coordination of autonomously driving vehicles,and to the characterization of the sustainability of such robotic systems.
展开▼
